package com.atguigu.srb.base.algorithm;

import org.springframework.util.StopWatch;

/**
 * @ClassName Solutions10
 * @Describe
 * @Author Wangchengshan
 * @Date 2023/6/26 13:12
 * @Version 1.0
 **/
public class Solutions10 {
    //最大得分
    //
    //有两个数组，每个数组内有序(从低到高)且不重复，
    //从数组下标0开始遍历，从左到右开始遍历，遍历到任意数组的末端结束，如果遇到两个数组有相同的元素可切换到另一条数组(也可以不换)(相同的元素只能记一次分),求所有可能合法路径中的最大得分。
    //
    //public int maxSum(int[] nums1, int[] nums2) {}
    //
    //输入：nums1 = [2,4,5,8,10], nums2 = [4,6,8,9]
    //输出：30  2+4+6+8+10 = 30
    //
    //输入：nums1 = [1,3,5,7,9], nums2 = [3,5,100]
    //输出：109
    //
    //输入：nums1 = [1,2,3,4,5], nums2 = [6,7,8,9,10]
    //输出：40
    //
    //输入：nums1 = [1,4,5,8,9,11,19], nums2 = [2,3,4,11,12]
    //输出：61

    public static int maxSum(int[] nums1, int[] nums2) {
        //两个分别相加，如果有相同元素，比较下一个元素大小
        //取相同元素之前或者两个相同元素之间最大值
        int sum1 = 0;
        int max = 0;
        int index2 = 0;
        int index1 = 0;
        int sum2 = 0;
        for (int i = 0; i < nums1.length; i++) {
            sum1 = sum1 + nums1[i];
            for (int i1 = index2; i1 < nums2.length; i1++) {
                sum2 = sum2 + nums2[i1];
                if (nums1[i] == nums2[i1]) {
                    max =   max + (sum1 > sum2 ? sum1 : sum2) ;
                    sum1 = 0;
                    sum2 = 0;
                    index2 = i1 +1 ;
                    break;
                }
                if(i1 == nums2.length-1 && i != nums1.length-1){
                    sum2 = 0;
                }
            }
            if(i == nums1.length-1){
                max = max + (sum1 > sum2 ? sum1 : sum2) ;
            }
        }
        return max == 0 ? sum1 > sum2 ? sum1 : sum2 : max;
    }

    public static void main(String[] args) {
        int[] num1 = {2, 4, 5, 8, 10};
        int[] num2 = {4, 6, 8, 9};
        int[] num3 = {1,3,5,7,9};
        int[] num4 = {3,5,100};
        int[] num5 = {1,2,3,4,5};
        int[] num6 = {6,7,8,9,10};
        int[] num7 = {1,4,5,8,9,11,19};
        int[] num8 = {2,3,4,11,12};
        StopWatch sw = new StopWatch("time");
        sw.start();
        int result = maxSum(num7, num8);
        sw.stop();
        System.out.println(result);
        System.out.println(sw.prettyPrint());
    }

}
